public class binarySearchTree {
    class TreeNode {
        private TreeNode left;
        private TreeNode right;
        private int val;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    //根结点
    public TreeNode root;

    //中序遍历二叉搜索树
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    //查找
    public boolean search(int key) {
        if (root == null) return false;
        TreeNode cur = root;
        while (cur != null) {
            //大于key就往左边找
            if (cur.val > key) {
                cur = cur.left;
            }
            //小于key往右边找
            else if (cur.val < key) {
                cur = cur.right;
            } else {
                //找到了
                return true;
            }
        }
        return false;
    }

    //插入
    public boolean add(int key) {
        TreeNode treeNode = new TreeNode(key);
        if (root == null) {
            root = treeNode;
            return true;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null) {
            if (cur.val < key) {
                prev = cur;
                cur = cur.right;
            } else if (cur.val > key) {
                prev = cur;
                cur = cur.left;
            } else {
                //cur.val==key 不能插入
                return false;
            }
        }
        //开始插入
        if (prev.val < key) {
            prev.right = treeNode;
        } else if (prev.val > key) {
            prev.left = treeNode;
        }
        return true;
    }
    //删除结点
    public void removeNode(TreeNode cur,TreeNode parent){
        //cur.val==key 找到了待删除元素
        //1.cur.left=null
        if (cur.left == null) {
            //1.cur=root
            if (cur == root) {
                root = root.right;
                //2.cur是parent的左孩子
            } else if (parent.left == cur) {
                parent.left = cur.right;
                //3.cur是parent的右孩子
            } else if (parent.right == cur) {
                parent.right = cur.right;
            }
        }

        //2. cur.right=null
        else if (cur.right == null) {
            //1.cur=root
            if (cur == root) {
                root = root.left;
                //2.cur是parent的左孩子
            } else if (parent.left == cur) {
                parent.left = cur.left;
                //3.cur是parent的右孩子
            } else if (parent.right == cur) {
                parent.right = cur.left;
            }
        }

        //3. cur.right!=null cur.left!=null
        else if (cur.right != null && cur.left != null) {
            //我们用方式1.找到cur的右子树最小值和cur替换
            //查找右子树最小值,最小值肯定没有左子树
            TreeNode tmpParent=cur;
            TreeNode tmp=cur.right;
            while (tmp.left!=null){
                //一直往左边走，找最小值，tmp.left为null时，tmp就是最小值
                tmpParent=tmp;
                tmp=tmp.left;
            }
            //覆盖
            cur.val=tmp.val;
            //删除tmp这个节点,tmp左子树肯定为null
            //判断tmp在tmpParent的左还是右
            if(tmpParent.left==tmp){
                tmpParent.left=tmp.right;
            }else if(tmpParent.right==tmp){
                tmpParent.right=tmp.right;
            }

        }
    }
    //删除操作
    public void remove(int key) {
        //cur用于查找待删除节点
        TreeNode cur = root;
        //parent记录cur的双亲结点，用于后续删除
        TreeNode parent = null;
        //查找到待删除元素
        while (cur != null) {
            if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else {
                removeNode(cur,parent);
                return;
            }
        }
    }
}



